// ----------------------------------------------------------------------------
// lock_free_stack.h
// ----------------------------------------------------------------------------
/*
 Description:
 基本的なロックフリースタックデータ構造用テンプレート. 
 このコンテナはbase/concurrentに依存している.
 注意 : このデータ構造はABA問題を考慮しない. (http://ja.wikipedia.org/wiki/ABA問題)
 */
#pragma once
#include <fw/base/core/noncopyable.h>
#include <fw/base/concurrent/atomic_counter.h>

namespace fw
{
	template< typename T > class Stack
	{
	private:
		
		class Node
		{
		public:
			T				m_data;
			Node*			m_next;
			Node( const T& data )
			: m_data( data )
			, m_next( 0 )
			{
			}
		}; // class Node 
		
		Node*				m_head;
		
	public:
		
		 Stack()
		: m_head( 0 )
		{
		}

		~Stack()
		{
			while(Size())
			{
				T dummy;
				Pop(&dummy);
			}
		}
		
		bool				Empty() const
		{
			return (m_head == 0);
		}
		
		size_t				Size() const
		{	// Note : This method is *not* thread safe. 
			volatile Node* p = m_head;
			size_t c=0;
			while (p!=0)
			{
				c++;
				p = p->m_next;
			}
			return c;
		}
		
		void				Clear()
		{	// Note : This method is *not* thread safe. 
			volatile Node* p = m_head;
			volatile Node* next;
			while(p)
			{
				next = p->m_next;
				delete p;
				p = next;
			}
		}
		
		void				Push( const T& data )
		{
			volatile Node* node = new Node( data );
			volatile Node* head;
			for(;;)
			{
				head = m_head;
				node->m_next = const_cast<Node*>(head);
				if(AtomicCasPtr(&m_head, (const void*)(head), (const void*)node))
				{
					return;
				}
			}
		}
		
		bool				Pop( T* data )
		{
			for(;;)
			{
				const Node* const head = m_head;
				if(!head)
				{
					m_head = 0;
					return false;
				}
				if(AtomicCasPtr(&m_head, head, head->m_next))
				{
					*data = head->m_data;
					delete head;
					return true;
				}
			}
		}
		
	}; // class Stack 
	
} // namespace fw 
